package Algorithm.Dp;

//https://leetcode-cn.com/problems/pizza-with-3n-slices/
//1388. 3n 块披萨
public class Leetcode1388_3n块披萨 {
    class Solution {
        public int maxSizeSlices(int[] slices) {
            int[] slices1 = new int[slices.length - 1];
            System.arraycopy(slices, 1, slices1, 0, slices.length - 1);
            int[] slices2 = new int[slices.length - 1];
            System.arraycopy(slices, 0, slices2, 0, slices.length - 1);
            int ans1 = calculate(slices1);
            int ans2 = calculate(slices2);
            return Math.max(ans1, ans2);
        }

        public int calculate(int[] slices) {
            int n = slices.length;
            int choose = (n + 1) / 3;
            int[][] dp = new int[n + 1][choose + 1];
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= choose; ++j) {
                    dp[i][j] = Math.max(dp[i - 1][j], (i - 2 >= 0 ? dp[i - 2][j - 1] : 0) + slices[i - 1]);
                }
            }
            return dp[n][choose];
        }
    }
}
